0086. 分隔链表【中等】

• 1. 📝 题目描述
• 2. 🎯 s.1 - 双链表拼接

1. 📝 题目描述

• leetcode

给你一个链表的头节点 head 和一个特定值 x，请你对链表进行分隔，使得所有 小于 x 的节点都出现在 大于或等于 x 的节点之前。

你应当 保留 两个分区中每个节点的初始相对位置。

---

示例 1：

输入：head = [1,4,3,2,5,2], x = 3
输出：[1,2,2,4,3,5]

示例 2：

输入：head = [2,1], x = 2
输出：[1,2]

---

提示：

• 链表中节点的数目在范围 [0, 200] 内
• -100 <= Node.val <= 100
• -200 <= x <= 200

2. 🎯 s.1 - 双链表拼接

c

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode* partition(struct ListNode* head, int x) {
    struct ListNode smallDummy = {0, NULL}, largeDummy = {0, NULL};
    struct ListNode* small = &smallDummy;
    struct ListNode* large = &largeDummy;

    while (head) {
        if (head->val < x) { small->next = head; small = small->next; }
        else { large->next = head; large = large->next; }
        head = head->next;
    }
    large->next = NULL;           // 断开大链表尾部
    small->next = largeDummy.next; // 拼接两段
    return smallDummy.next;
}

js

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} head
 * @param {number} x
 * @return {ListNode}
 */
var partition = function (head, x) {
  const smallDummy = new ListNode(0)
  const largeDummy = new ListNode(0)
  let small = smallDummy,
    large = largeDummy

  while (head) {
    if (head.val < x) {
      small.next = head
      small = small.next
    } else {
      large.next = head
      large = large.next
    }
    head = head.next
  }
  large.next = null // 断开大链表尾部
  small.next = largeDummy.next // 拼接两段
  return smallDummy.next
}

py

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def partition(self, head: Optional[ListNode], x: int) -> Optional[ListNode]:
        small_dummy = ListNode(0)
        large_dummy = ListNode(0)
        small, large = small_dummy, large_dummy

        while head:
            if head.val < x: small.next = head; small = small.next
            else: large.next = head; large = large.next
            head = head.next
        large.next = None             # 断开大链表尾部
        small.next = large_dummy.next  # 拼接两段
        return small_dummy.next

• 时间复杂度：$O(n)$，其中 n 是链表长度，只需遍历一次
• 空间复杂度：$O(1)$，只使用常数额外空间

算法思路：

• 创建两个哨兵链表 small 和 large，分别收集小于 x 和大于等于 x 的节点
• 遍历原链表，将节点分配到对应链表
• 遍历结束后，将大链表尾部置空，小链表尾部接上大链表头部